package org.example.y24.m11;

import java.util.ArrayList;
import java.util.List;

public class HorseJump {

    private static final int MAX_SIZE = 9; // 棋盘大小
    private static final int MIN_SIZE = 5;
    private int[][] board; // 棋盘状态
    private List<List<String>> allRoutes; // 存储所有路径

    public HorseJump() {
        board = new int[MIN_SIZE][MAX_SIZE];
        for (int i = 0; i < MIN_SIZE; ++i) {
            for (int j = 0; j < MAX_SIZE; ++j) {
                board[i][j] = 0; // 初始化为0，表示空位
            }
        }
        allRoutes = new ArrayList<>(); // 初始化路径列表
    }

    // 判断当前位置是否可以跳
    private boolean isValidMove(int x, int y, int nextX, int nextY) {
        return nextX >= 0 && nextX < MIN_SIZE && nextY >= 0 && nextY < MAX_SIZE && board[nextX][nextY] == 0;
    }

    // 马的八个可能移动方向
    private List<Pair<Integer, Integer>> generateMoves() {
        List<Pair<Integer, Integer>> allMoves = new ArrayList<>();
        allMoves.add(new Pair<>(2, 1));
        allMoves.add(new Pair<>(1, 2));
        allMoves.add(new Pair<>(-1, 2));
        allMoves.add(new Pair<>(-2, 1));
        allMoves.add(new Pair<>(2, -1));
        allMoves.add(new Pair<>(1, -2));
        allMoves.add(new Pair<>(-1, -2));
        allMoves.add(new Pair<>(-2, -1));
        return allMoves;
    }
    private void backtrack(int x, int y, List<String> route) {
        if (x == MIN_SIZE - 1 && y == MAX_SIZE - 1) { // 如果到达终点
            allRoutes.add(new ArrayList<>(route)); // 保存当前路径
            return;
        }

        board[x][y] = 1; // 标记当前位置已访问
        List<Pair<Integer, Integer>> moves = generateMoves();
        for (Pair<Integer, Integer> move : moves) {
            int nextX = x + move.getKey();
            int nextY = y + move.getValue();

            if (isValidMove(x, y, nextX, nextY) && !isBackwardMove(x, y, nextX, nextY)) {
                route.add(nextX + "," + nextY);
                backtrack(nextX, nextY, route); // 递归遍历下一个位置
                route.remove(route.size() - 1); // 回溯，移除路径
            }
        }
        board[x][y] = 0; // 回溯，恢复当前位置状态
    }

    // 判断是否是向左移动
    private boolean isBackwardMove(int x1, int y1, int x2, int y2) {
        return x2 < x1 || (x2 == x1 && y2 < y1);
    }

    // 打印跳行路线
    private void printRoutes() {
        for (List<String> route : allRoutes) {
            for (int i = 0; i < route.size(); ++i) {
                if (i > 0) System.out.print("->");
                System.out.print(route.get(i));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        HorseJump horseJump = new HorseJump();
        List<String> route = new ArrayList<>();
        route.add("0,0"); // 起始位置
        horseJump.backtrack(0, 0, route);
        horseJump.printRoutes();
    }

    // 辅助类，用于表示一对整数
    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}